MODELS OF EVENT NONDETERMINISTIC AUTOMATA FOR REPRESENTATION OF CONTROL
ALGORITHMS OF INTERACTING PROCESSES IN MULTIPROCESSOR SYSTEMS BASED
ON THE USE OF THE MONITOR MECHANISMS 

Volchikhin Vladimir Ivanovich, Doctor of engineering sciences, professor, president of Penza State University
(Penza, 40 Krasnaya str.), rectorat@pnzgu.ru
Vashkevich Nikolay Petrovich, Doctor of engineering sciences, professor, sub-department of computer science, Penza State University (Penza, 40 Krasnaya str.), vt@alice.pnzgu.ru
Biktashev Ravil' Aynulovich, Candidate of engineering sciences, professor, sub-department of computing machines and systems, Penza State Technological Academy (Penza, 1a Baydukova passage), bra559620@sura.ru

681.3.012

The aim of the paper is to develop the methodology of formal description of the control algorithm for interacting parallel processes during the exchange of messages between them that includes the use of the monitor, the ring buffer and the "producers-consumers” sample task. The study is based on the method of event nondeterministic automata (ENDA), which allows to express the control algorithm in a simple and compact form as a quantifier-free system of recurrent canonical equations (SRCE describes all private events that have been implemented in the control system). A distinctive feature of the method ENDA is that the system (SRCE), which represents the transition function in the control algorithm is not described in terms of states of deterministic automata (DA), and in terms of private events NDA, the simultaneous existence of which determines the status of an equivalent DA. Since the number of ENDA private events is much smaller than the number of states of DA equivalent to it, then the description of the control algorithm in the language of ENDA will be significantly easier. The presented method of the formal description of the private events control algorithm in distributed messagepassing multiprocessor system, and the language of the ENDA provides realization of the basic properties necessary for the control system: absence of deadlocks (lack of conflicts) and justice (no endless waiting and searching in the monitor for the processes accessing the shared resource). Analytical representation of the control algorithm by the interacting parallel processes as a system of SRCE allows to perform a simple transformation of the description of the control algorithm for hardware description languages (e. g., VHDL) to verify the algorithm and its hardware
implementation using PLD, which in turn provides greater reliability and performance of messages transmission systems. 

control algorithm, interacting parallel processes, event nondeterministic automata, «producers-consumers» task, monitor mechanisms. 

1. Deytel G. Vvedenie v operatsionnye sistemy : v 2-kh t. [Introduction into operative systems: in 2 vol.]. Moscow: Mir, 1987, vol. 1, 359 p.
2. Solov'ev G. I., Nikitin V. D. Operatsionnye sistemy EVM : ucheb. posobie [Computer operational systems: tutorial]. Moscow: Vyssh. shk., 1988, 207 p.
3. Hoare C. A. R. Erratum in Commun. Of the ACM. 1975, vol. 18, p. 95.
4. Brinch Hansen P. IEEE Trans. On Software Engineering. 1975, vol. SE-1, pp. 199–207.
5. Endryus G. R. Osnovy mnogopotochnogo i raspredelennogo programmirovaniya [Basics of multithreaded and dispense programming]. Moscow: Vil'yams, 2003, 512 p.
6. Tanenbaum E. Sovremennye operatsionnye sistemy [Modern operational systems]. Saint Petersburg: Piter, 2002, 1040 p.
7. Vashkevich N. P. Nedeterminirovannye avtomaty v proektirovanii sistem parallel'noy obrabotki: ucheb. posobie [Nondeterministic automata in parallel processing systems design: tutorial]. Penza: Izd-vo Penz. gos. un-ta, 2004, 280 p.
8. Vashkevich N. P., Biktashev R. A., Tarakanov A. A. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Tekhnicheskie nauki [University proceedings. Volga region. Engineering sciences]. 2007, no. 4, pp. 98–107.
9. Klark E. M., Gramberg O., Peled D. Verifikatsiya modeley programmy: Model Checking [Verification of program models: Model checking]. Moscow: MTsNMO, 2002, 416 p.
10. Vashkevich N. P., Biktashev R. A., Gurin E. I. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Tekhnicheskie nauki [University proceedings. Volga region. Engineering sciences]. 2007, no. 2, pp. 3–12.
11. Keylingert P. Elementy operatsionnykh sistem [Operational system elements]. Moscow: Mir, 1985, 295 p.